#！/usr/bin/env python
#!coding=utf-8

import os
from platform import node
from queue import Queue
import sys

class TreeNode:
    def __init__(self, val) -> None:
        self.val = val
        self.left = None
        self.right = None

class Tree:
    def __init__(self) -> None:
        self.root = None
    def initTreeByList(self, _list):
        self.root,_ = self.buildTree(_list, 0)
        #print(self.root.val)
        print("Tree is ok")
    def echoNode(self, current):
        if current == None:
            return "-1"
        else:
            return str(current.val)
    def buildTree(self, _list, _index):
        #其实就是通过中序遍历的方式还原二叉树
        #print(len(_list), _index)
        if len(_list) > _index:
            #print("-----")
            if (_list[_index] == -1):
                return None,_index
            else:
                current = TreeNode(_list[_index])
                _index = _index + 1
                current.left, _index = self.buildTree(_list, _index)
                
                _index = _index + 1
                current.right, _index = self.buildTree(_list, _index)
                #line = str(current.val) + "->" + self.echoNode(current.left) + "|" + self.echoNode(current.right)
                #print(line)
                return current, _index
        else:
            return None,_index

    def levelTraverse(self):
        current = self.root
        result = []
        #current = self.root
        myQueue = Queue()
        myQueue.put(self.root)
        num = 1
        counter = 0
        data = []
        while not myQueue.empty():
            #print(myQueue.)
            current = myQueue.get()
            #print("current node is %d" %(current.val))
            #myQueue.
            num = num - 1
            data.append(current.val)
            if current.left != None:
                counter = counter + 1
                myQueue.put(current.left)
            if current.right != None:
                counter = counter + 1
                myQueue.put(current.right)
            if num == 0:
                num = counter
                counter = 0
                result.append(data)
                data = []
        for line in result:
            print(line)

            
    def preOrderReTraverse(self, _root, data):
        if _root == None:
            pass
        else:
            data.append(_root.val)
            if _root.left != None:
                self.preOrderReTraverse(_root.left, data)
            if _root.right != None:
                self.preOrderReTraverse(_root.right, data)
    def preOrderIterationTraverse(self, _root):
        nodeList = []
        data = []
        if _root == None:
            return data
        nodeList.append(_root)
        while len(nodeList) > 0:
            current = nodeList[-1]
            nodeList.pop()
            data.append(current.val)
            if current.right != None:
                nodeList.append(current.right)
            if current.left != None:
                nodeList.append(current.left)
        return data

    def midOrderReTraverse(self, _root, data):
        if _root == None:
            pass
        else:
            
            if _root.left != None:
                self.midOrderReTraverse(_root.left, data)
            data.append(_root.val)
            if _root.right != None:
                self.midOrderReTraverse(_root.right, data)
    def midOrderIterationTraverse(self, _root):
        nodeList = []
        data = []
        if _root == None:
            return data
        current = _root
        while current != None or len(nodeList) !=0:
            
            while current != None:
                nodeList.append(current)
                current = current.left
            current = nodeList.pop()
            #print(current.val)
            data.append(current.val)
            current = current.right

        return data
    def posOrderReTraverse(self, _root, data):
        if _root == None:
            pass
        else:
            if _root.left != None:
                self.posOrderReTraverse(_root.left, data)
            if _root.right != None:
                self.posOrderReTraverse(_root.right, data)
            data.append(_root.val)
    def posOrderIterationTraverse(self, _root):
        nodeList = []
        data = []
        if _root == None:
            return data
        nodeList.append(_root)
        while len(nodeList) > 0:
            current = nodeList[-1]
            nodeList.pop()
            data.append(current.val)
            if current.left != None:
                nodeList.append(current.left)
            if current.right != None:
                nodeList.append(current.right)
        data.reverse()
        return data

def testQueue():
    dt = Queue()
    for i in range(10):
        dt.put(i)
    print(dt.queue)
    print(dt.get())
    print(dt.queue)
    data = list(range(10))
    print(data)
    data.sort(key=lambda x:x, reverse=False)
    #data = sorted(data, key=lambda x:x, reverse=True)
    #data.reverse()
    print(data)

def run():
    #testQueue()
    print("hello")
    data = [1, -1, 2, 3, -1, -1, 4, -1, -1]
    #data = [1, 2, -1, -1, 3, -1, 4, -1, -1]
    print("init the tree")
    myTree = Tree()
    myTree.initTreeByList(data)
    myTree.levelTraverse()

    print("preorder traverse ....................")
    result = []
    myTree.preOrderReTraverse(myTree.root, result)
    print(result)

    result = []
    result = myTree.preOrderIterationTraverse(myTree.root)
    print(result)

    print("midorder traverse ....................")
    result = []
    myTree.midOrderReTraverse(myTree.root, result)
    print(result)
    result = []
    result = myTree.midOrderIterationTraverse(myTree.root)
    print(result)

    print("posorder traverse ....................")
    result = []
    myTree.posOrderReTraverse(myTree.root, result)
    print(result)
    result = []
    result = myTree.posOrderIterationTraverse(myTree.root)
    print(result)

if __name__ == "__main__":
    run()
    #testQueue()